#pragma once 
#include <algorithm>
#include "reverse_iterator.h"

namespace qds
{
    template<class T>
    struct list_node
    {
        list_node(const T& data = T())
            :_next(nullptr)
            , _prev(nullptr)
            , _data(data)
        {}

        list_node<T>* _next;
        list_node<T>* _prev;
        T _data;
    };

    //用两份代码实现list的迭代器实在是代码有些冗余
    //他们之间的区别除了返回值和名字的,基本保持一致
    //这里没有体现c++的泛型编程,所以我们用模板实现一份
    //template<class T>
    //struct __list_iterator
    //{
    //    typedef list_node<T> node;
    //    node* _node;

    //    __list_iterator(node* x = nullptr)
    //        :_node(x)
    //    {}

    //    T& operator*() const
    //    {
    //        return _node -> _data;
    //    }

    //    //前置++
    //    __list_iterator& operator++()
    //    {
    //        _node = _node -> _next;
    //        return *this;
    //    }

    //    //后置++
    //    __list_iterator operator++(int)
    //    {
    //        __list_iterator<T> tmp(*this);
    //        _node = _node -> _next;
    //        return tmp;
    //    }
    //    
    //    //前置--
    //    __list_iterator& operator--()
    //    {
    //        _node = _node->_prev;
    //        return *this;
    //    }

    //    //后置--
    //    __list_iterator operator--(int)
    //    {
    //        __list_iterator<T> tmp(*this);
    //        _node = _node->_prev;
    //        return tmp;
    //    }

    //   bool operator==(const __list_iterator<T>& it) const
    //   {
    //       return it._node == _node;
    //   }

    //   bool operator!=(const __list_iterator<T>& it) const
    //   {
    //       return it._node != _node;
    //   }

    //};


    //template<class T>
    //struct __const_list_iterator
    //{
    //    typedef list_node<T> node;
    //    node* _node;

    //    __const_list_iterator(node* x = nullptr)
    //        :_node(x)
    //    {}

    //    const T& operator*() const
    //    {
    //        return _node -> _data;
    //    }

    //    //前置++
    //    __const_list_iterator& operator++()
    //    {
    //        _node = _node -> _next;
    //        return *this;
    //    }

    //    //后置++
    //    __const_list_iterator operator++(int)
    //    {
    //        __list_iterator<T> tmp(*this);
    //        _node = _node -> _next;
    //        return tmp;
    //    }
    //    
    //    //前置--
    //    __const_list_iterator& operator--()
    //    {
    //        _node = _node->_prev;
    //        return *this;
    //    }

    //    //后置--
    //    __const_list_iterator& operator--(int)
    //    {
    //        __list_iterator<T> tmp(*this);
    //        _node = _node->_prev;
    //        return tmp;
    //    }

    //   bool operator==(const __const_list_iterator<T>& it) const
    //   {
    //       return it._node == _node;
    //   }

    //   bool operator!=(const __const_list_iterator<T>& it) const
    //   {
    //       return it._node != _node;
    //   }

    //};

    //首先我们先用两个模板参数来试试实现list的迭代器
    //但是如果我们使用两个模板参数来实现的话,运算符->的重载就不能实现
    //仔细想想如果链表里面存储的是内置类型的话,那么是没有问题的,
    //可以直接用*,修改内容,如果是自定义类型,那么*就不行,*只是取到对象
    //要.才能访问对象里面的成员变量(假如是公有的话),也可以直接->
    //所以我们需要实现->的重载
    //因为->的返回值是node* ,同时考虑到const_iterator
    //所以我们又引入一个模板参数

    //template<class T, class Ref>
    //struct __list_iterator 
    //{
    //    typedef list_node<T> node;
    //    node* _node;

    //    __list_iterator(node* x = nullptr)
    //        :_node(x)
    //    {}

    //    Ref operator*() const 
    //    {
    //        return _node->_data;
    //    }

    //    __list_iterator<T, Ref>& operator++()
    //    {
    //        _node = _node->_next;
    //        return *this;
    //    }

    //    __list_iterator<T, Ref> operator++(int)
    //    {
    //        __list_iterator<T, Ref> tmp(*this);
    //        _node = _node->_next;
    //        return tmp;
    //    }

    //    __list_iterator<T, Ref>& operator--()
    //    {
    //        _node = _node->_prve;
    //        return *this;
    //    }

    //    __list_iterator<T, Ref> operator--(int)
    //    {
    //        __list_iterator<T, Ref> tmp(*this);
    //        _node = _node->_prev;
    //        return tmp;
    //    }

    //    bool operator==(const __list_iterator<T, Ref>& it) const
    //    {
    //        return _node == it._node;
    //    }

    //    bool operator!=(const __list_iterator<T, Ref>& it) const 
    //    {
    //        return _node != it._node;
    //    }
    //    
    //};

    //用三个模板参数来实现list的迭代器
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef list_node<T> node;
        //名字太长,为了方便,重命名一下
        typedef __list_iterator<T, Ref, Ptr> self;
        //为了外部能够访问类模板的参数,所以这里需要进行typedef
        typedef Ref reference;
        typedef Ptr pointer;

        node* _node;

        //我们思考一下,迭代器的拷贝构造和赋值重载还有析构函数是否需要我们自己去实现?
        //首先是拷贝构造和复制重载,都是属于浅拷贝,所以默认生成的就可以了
        //然后是析构函数,迭代器是借助节点的指针访问修改链表
        //节点属于链表,不属于迭代器,所以它不管释放
        //所以不需要自己实现,默认生成的就可以了

        __list_iterator(node* x = nullptr)
            :_node(x)
        {}

        Ref operator*() const
        {
            return _node->_data;
        }

        Ptr operator->() const
        {
            return &(_node->_data);
        }

        self& operator++()
        {
            _node = _node->_next;
            return *this;
        }

        self operator++(int)
        {
            self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }

        self operator--(int)
        {
            self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        bool operator==(const self& it) const
        {
            return it._node == _node;
        }

        bool operator!=(const self& it) const
        {
            return it._node != _node;
        }
    };

    template<class T>
    class list
    {
        typedef list_node<T> node;

    public:
        //一个模板参数
        //typedef __list_iterator<T> iterator;
        //typedef __const_list_iterator<T> const_iterator;

        //两个模板参数
        //typedef __list_iterator<T, T&> iterator;
        //typedef __list_iterator<T, const T&> const_iterator;

        //三个模板参数
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;

        //这种写法是错误的,原因是reverse_iterator已经在上面typedef过了
        //所以下面就不是去调用的模板,而是上面typedef过的
        //所以有三种解决办法
        //1.下面的reverse_iterator加上qds::,指定命名空间,编译器就会去命名空间里面寻找类模板
        //2.先typedef const_reverse_iterator ,这个时候会去qds的命名空间里面找
        //3.有时linux编译器抽风,vs没报错,g++报错了,这个时候,两者都加上qds::,指定命名空间,那么肯定不会出错
        //所以以后出现类似的场合,记得全部加上命名空间
        
        //1.
        //typedef reverse_iterator<iterator, T&, T*> reverse_iterator;
        //typedef qds::reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

        //2.
        //typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
        //typedef qds::reverse_iterator<iterator, T&, T*> reverse_iterator;
        
        //3.第一种写法
        typedef qds::reverse_iterator<iterator, T&, T*> reverse_iterator;
        typedef qds::reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

        //3.第二种写法
        //typedef qds::reverse_iterator<iterator> reverse_iterator;
        //typedef qds::reverse_iterator<const_iterator> const_reverse_iterator;

        //类型的意义,类型的力量
        //node*原生指针和一个迭代器对象,他们占用空间是一样大的
        //32位下都是4byte,并且存储的值也是一样的.
        //但是对它们使用运算符的意义和结果是不一样的
        //void func()
        //{
        //    node* pnode = _head->_next;
        //    iterator it = _head->_next;

        //    //获取到pnode指向的节点的内容
        //    *pnode;
        //    //获取到迭代器指向的节点的数据
        //    *it;

        //    //pnode = pnode + sizeof(pnode)
        //    ++pnode;
        //    //指向下一个节点
        //    ++it;
        //}

        void create_head()
        {
            _head = new node();
            _head->_next = _head;
            _head->_prev = _head;
        }

        list()
        {
            create_head();
        }

        list(int n, const T& val = T())
        {
            create_head();
            for (int i = 0; i < n; ++i)
            {
                push_back(val);
            }

        }

        //当你这样初始化的时候(list<int> lt(2, 250))
        //不会调用下面的这个构造函数,而是去调用下下面的模板函数
        //int和size_t类型不一样,所以编译前不会优先调用
        //因为2和250在编译器看来,类型一样的,都是int
        //所以会优先去用模板推演,因为模板的两个参数是一样的
        //你自己增加一个上面的函数,有int的参数,编译器会吃现成的
        //而不会去推演
        list(size_t n, const T& val = T())
        {
            create_head();
            for (size_t i = 0; i < n; ++i)
            {
                push_back(val);
            }

        }

        template<class input_iterator>
        list(input_iterator first, input_iterator last)
        {
            create_head();
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        //拷贝构造函数的现代写法
        list(const list<T>& lt)
        {
            create_head();
            list<T> tmp(lt.begin(), lt.end());
            std::swap(_head, tmp._head);
        }

        ////传统的拷贝构造函数
        //list(const list<T>& lt)
        //{   
        //    create_head(); 
        //    for (const T& e : lt)
        //    {
        //        push_back(e);
        //    }
        //}

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            //iterator it = begin();
            //while(it != end())
            //{
            //    iterator del = it++;
            //    delete del._node;
            //}

            ////记得最后头节点指向自己
            //_head->_next = _head;
            //_head->_prev = _head;

            //对erase可以进行复用
            iterator it = begin();
            while (it != end())
            {
                //erase会自动解决节点之间的链接关系,不用担心头节点的问题
                erase(it++);
            }

        }

        iterator begin()
        {
            return iterator(_head->_next);
        }

        iterator end()
        {
            return iterator(_head);
        }

        const_iterator cbegin() const
        {
            return const_iterator(_head->_next);
        }

        const_iterator cend() const
        {
            return const_iterator(_head);
        }

        reverse_iterator rbegin()
        {
            return reverse_iterator(end());
        }

        reverse_iterator rend()
        {
            return reverse_iterator(begin());
        }

        const_reverse_iterator crbegin() const
        {
            return reverse_iterator(end());
        }

        const_reverse_iterator crend() const
        {
            return reverse_iterator(begin());
        }

        //赋值重载的现代写法
        list<T>& operator=(list<T> lt)
        {
            std::swap(_head, lt._head);
            return *this;
        }

        ////赋值重载的传统写法
        //list<T>& operator=(const list<T>& lt)
        //{
        //    if (this != &lt)
        //    {
        //        clear();
        //        for (const T& e : lt)
        //        {
        //            push_back(e);
        //        }
        //    }
        //    return *this;
        //}

        void push_back(const T& x)
        {
            //先找到尾
            //node* tail = _head -> _prev;
            ////new一个新节点
            //node* new_node = new node(x);
            ////尾的节点指向新节点
            //tail -> _next = new_node;
            ////新节点指向尾
            //new_node -> _prev = tail;
            ////新节点指向头
            //new_node -> _next = _head;
            ////头指向新节点
            //_head -> _prev = new_node;

            //可以对insert进行复用
            insert(end(), x);
        }

        void pop_back()
        {
            erase(--end());
        }

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        void pop_front()
        {
            erase(begin());
        }

        //这里insert以后,pos是否会失效?
        //不会失效,因为指向的哪个节点没有任何改变,所以迭代器有效
        iterator insert(iterator pos, const T& x)
        {
            node* cur = pos._node;
            node* prev = cur->_prev;
            node* new_node = new node(x);

            prev->_next = new_node;
            new_node->_prev = prev;
            new_node->_next = cur;
            cur->_prev = new_node;

            //返回新插入节点的位置
            return iterator(new_node);
        }

        //这里erase以后,pos是否失效?
        //一定失效,因为这里的节点会被释放掉
        iterator erase(iterator pos)
        {
            //插入是可以在头节点进行插入的,但是你删除却不能干掉头节点
            assert(pos._node != _head);

            node* next = pos._node->_next;
            node* prev = pos._node->_prev;
            delete pos._node;
            prev->_next = next;
            next->_prev = prev;

            //返回删除节点的下一个节点的位置
            return iterator(next);
        }

    private:
        //只需要有一个头节点的指针就行了
        node* _head;
    };
}
